Cyclic redundancy check (CRC) is a common technique for detecting data transmission errors. Transmitted messages are divided into predetermined lengths that are then divided by a fixed divisor. According to the calculation, the remainder number is appended onto and sent with the message. When the message is received, the computer recalculates the remainder and compares it to the transmitted remainder. If the numbers do not match, an error is detected.
For example, in a data networking system a message is sent in binary form from a transmitter to a receiver through a medium. Errors can get introduced, in the message, which are random in nature due to noise present in the medium. Errors may be detected if a signature is sent along with message and it is compared at the receive side with the recreated signature. A simple way to accomplish this is to add a checksum to the message bytes. For example:
Message:FA 12 C7 D6Addition:2A9Modulo 256 Checksum:A9Text Message and Checksum:FA 12 C7 D6 A9
There are many possible scenarios of data corruption. In one example, the data is corrupted and the checksum is intact. That is, the received message may be “FA 12 C2 D6 A9” and the receiver re-calculates the checksum as “A4” which does not match with the “A9” checksum. Thus, the data packet can be discarded.
In another example, the data is intact but the checksum is corrupt. That is, the received message with checksum is “FA 12 C7 D6 A2.” When the receiver re-calculates the checksum as “A9,” which does not match with the received checksum of “A2,” the packet has an error and can be discarded.
In a third example, the data as well as the checksum is corrupt. In most cases this will result in the packet being discarded but once in a while corruption will be such that the recreated checksum will match the corrupted checksum. Such a situation is extremely rare and highly unlikely. Unfortunately this potentiality for error with checksum processing can not be avoided and the only solution to further reduce this possibility is to widen the checksum width.
Another problem with checksum processing, is that specific CRC circuitry within hardware or CRC engines are needed for a variety of possible byte lengths (data widths). Generally, this is not an issue when received messages have greater lengths than the receiving device's CRC generators (also called CRC calculators). So, a received message of 16 bytes (128 bit word) can be evaluated by using combinations of CRC generators having 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, and 1 processing widths.
It is also problematic when a device lacks a small enough CRC calculator to handle received messages of smaller data widths. For example, if device has only a 6 byte wide CRC engine and a received message is 4 bytes, then more CRC calculators and processing complexity are needed to handle such message data widths. Typically, a solution to this is to have CRC calculators with data widths as small as a single byte. Yet, this is inefficient and costly approach. Implementations with multiple CRC calculators have drawbacks associated with processing latency, integration complexity, and deployment in limited space devices.
Therefore, improved techniques for CRC processing are desirable.